import java.util.Arrays;

/**
 * Created With IntelliJ IDEA
 * Description:牛客网: BM59 N皇后问题
 * <a href="https://www.nowcoder.com/practice/c76408782512486d91eea181107293b6?tpId=295&tqId=1008753&ru=/exam/company&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Fcompany">...</a>
 * User: DELL
 * Data: 2023-04-29
 * Time: 22:37
 */
public class Solution {
    /**
     * 解题思路 (递归+回溯)
     * 我觉得本题最关键的是要发现一个隐藏的条件,就是本题是要在 n*n 的棋盘上摆上 n 个皇后,
     * 且每个皇后都要单独占一行和一列,即每一行和每一列上均有且只有一个皇后,因此基于这样分析
     * 以后,就有了递归的雏形,即我们选择放上去一个 皇后 后,那一行和那一列就均被占用了,即变
     * 成了 n-1 阶的问题,因此基于以上的想法基本确定该题使用递归+回溯的解法.
     * 这样子写之后,因为要记录之前已经确定好的皇后的行号的列号,同时不想使用更多的空间,这里
     * 学习到了一个方法,定义一个 pos 数组,每次我们选定一个皇后的位置后,我们就将皇后对应的
     * 列号 作为 pos[行号] 的值,即 pos[i] 的含义是有一个皇后的坐标为(i,pos[i]),同时
     * 初始化 pos 数组的值为 -1 即可.
     * @param n
     * @return
     */
    public int Nqueen (int n) {
        //检查合法性
        if (n <= 0) {
            return 0;
        }
        //标记皇后位置的数组
        int[] pos = new int[n];
        //初始化pos数组
        Arrays.fill(pos,-1);
        //递归查找摆放的样式数量
        return recursion(pos,0,n);
    }


    /**
     * 递归查找摆放的样式数量
     * @param pos     标记已经确定的皇后位置的数组
     * @param curRow  标记当前正在确定第几行的皇后
     * @param n       问题的规模
     * @return        满足条件的样式数量
     */
    private int recursion(int[] pos, int curRow, int n) {
        if (curRow == n) {
            return 1;
        }
        //记录后序有多少种拜访方法可以满足条件
        int res = 0;
        //遍历验证每一种情况
        for (int col = 0; col < n; col++) {
            if (!isValid(pos,curRow,col)) {
                continue;
            }
            pos[curRow] = col;
            res += recursion(pos,curRow+1,n);
            //回溯
            pos[curRow] = -1;
        }
        return res;
    }

    /**
     * 判断合法性
     * @param pos   标记已经确定的皇后位置的数组
     * @param row   皇后的行号
     * @param col   皇后的列号
     * @return
     */
    private boolean isValid(int[] pos, int row, int col) {
        //不可以同一行
        if (pos[row] != -1) {
            return false;
        }
        //不可以同一列,同一条斜线
        for (int i = 0; i < pos.length; i++) {
            if (pos[i] != -1) {
                if (pos[i] == col || Math.abs(row-i) == Math.abs(col-pos[i])) {
                    return false;
                }
            }
        }
        return true;
    }
}